συνδυαστικός λογισμός

Είναι γνωστός και ως συνδυαστική ανάλυση. Κλάδος της αριθμητικής, που εξετάζει τις διάφορες δυνατές ομαδοποιήσεις με διάφορα αντικείμενα ή σύμβολα. Αν έχουμε τρεις σφαίρες με διαφορετικό χρώμα (άσπρο, κόκκινο, πράσινο) και θέλουμε να σχηματίσουμε ζεύγη με αυτές, τα δυνατά ζεύγη είναι τρία (άσπρο - κόκκινο, άσπρο - πράσινο, κόκκινο - πράσινο). Αν όμως μας ενδιαφέρει και η τάξη των χρωμάτων στα ζεύγη, τα ζεύγη θα είναι 6, δηλαδή τα τρία προηγούμενα και άλλα 3 με την αντίστροφη τάξη (το ζεύγος άσπρο - κόκκινο και το κόκκινο - άσπρο). Είναι προφανές ότι ο τρόπος ή η τάξη σύζευξης δεν εξαρτιούνται από τη φύση των στοιχείων. Μεταθέσεις. Αν έχουμε αντικείμενα (έστω τα α₁, α₂, α₃ ... α_ν), ονομάζουμε μεταθέσεις αυτών το πλήθος των δυνατών αλλαγών στις θέσεις τους, ώστε κάθε φορά να βρίσκονται σε διαφορετική τάξη. Ο αριθμός των μεταθέσεων ν αντικειμένων είναι 1 x 2 x 3 x ... ν (γράφεται και ν! που ονομάζεται παραγωγικό του ν). Οι δυνατές μεταθέσεις δύο στοιχείων, έστω Α και Β, είναι προφανώς οι AB και ΒΑ, δηλαδή 2! = 1. 2 = 2. Οι μεταθέσεις τριών στοιχείων, έστω A, B, Γ, είναι: ΑΒΓ, ΑΓΒ, ΒΑΓ, ΓΑΒ, ΓΒΑ, δηλαδή 3! 1 x 2 x 3 = 6. Παραδείγματα: Έξι άτομα μπορούν να καθήσουν σ’ ένα τραπέζι κατά 720 διαφορετικούς τρόπους (6! = 1 x 2 x 3 x 4 x 5 x 6 = 720)· με τα πέντε γράμματα α, β, γ, δ, ε, είναι δυνατό να σχηματιστούν 120 λέξεις (5! = 1 x 2 x 3 x 4 x 5 = 120)· στα 10 βαγόνια ενός συρμού είναι δυνατό να υπάρξουν 3.628.800 μεταθέσεις. Διατάξεις. Αν έχουμε ν αντικείμενα και θέλουμε να σχηματίσουμε ομάδες Κ αντικειμένων από αυτά τα ν, το πλήθος των δυνατών ομαδοποιήσεων τα ονομάζουμε διατάξεις (τάξης Κ επί ν αντικειμένων, εφόσον Κν), θεωρώντας διάφορες δύο ομαδοποιήσεις, όχι μόνο όταν περιέχουν διάφορα στοιχεία, αλλά ακόμα και αν περιέχουν τα αυτά στοιχεία αλλά σε διαφορετική τάξη. Προφανώς οι διατάξεις ν τάξης των ν αντικειμένων συμπίπτουν με τις μεταθέσεις αυτών των στοιχείων. Οι διατάξεις τάξης 1 αποτελούνται από τα ν στοιχεία (α₁, α₂ α₃,... α_ν) λαμβανόμενα μεμονωμένα. Για να έχουμε όλες τις διατάξεις τάξης 2 αρκεί να συνδυάσουμε συνεχώς κάθε στοιχείο με καθένα από τα υπόλοιπα ν - 1. Οι δυνατές διατάξεις είναι συνεπώς v(v-1). Έτσι οι διατάξεις τάξης 2 επί 5 αντικειμένων είναι 5. (5-1), δηλαδή 20· τάξης 3 επί ν στοιχείων είναι v(v-1) (v-2). Γενικά ο αριθμός των διατάξεων τάξης Κ επί ν αντικειμένων είναι: Δ_ν,Κ = v(v-l) (v-2) ... (v-K + 1). Παραδείγματα : Σ’ ένα διαμέρισμα βαγονιού με οχτώ θέσεις υπάρχουν πέντε επιβάτες· κατά πόσους διαφορετικούς τρόπους μπορούν να καθήσουν; Είναι δηλαδή ο αριθμός των διατάξεων τάξης 5 επί 8 στοιχείων: Δ_8,5= 8 x 7 x 6 x 5 x 4 = 6.720. Πόσοι είναι οι τριψήφιοι αριθμοί μεταξύ του 100 και του 1.000, που αποτελούνται από διαφορετικά στοιχεία μεταξύ τους, και από το μηδέν; Είναι Δ_9,3= 9 x 8 x 7 = 504. Σ’ έναν διαγωνισμό για 4 θέσεις συμμετέχουν 25 υποψήφιοι: ποιες είναι οι δυνατές διατάξεις των επιτυχόντων; Δ_25,4= 25 x 24 x 23 x 22 = 303.606 διατάξεις. Συνδυασμοί. Είναι οι διατάξεις υπό την προϋπόθεση ότι θεωρούνται όμοιες δύο ομάδες, όταν αποτελούνται από τα αυτά στοιχεία άσχετα της κατάταξης τους. Αποδείχνεται εύκολα ότι ο αριθμός των συνδυασμών τάξης Κ επί ν στοιχείων είναι: Σ_ν+κ = v(v-1) (v-2) ... (ν-Κ+1) / K! Παράδειγμα:Σε μια τράπουλα με 52 κάρτες, αν ο κάθε παίχτης παίρνει πέντε κάρτες μαζί, πόσοι είναι οι δυνατοί συνδυασμοί, για τον πρώτο παίχτη; για το δεύτερο είναι: Επαναλήψεις. Μεταθέσεις με επανάληψη επί ν αντικειμένων τάξης Κ είναι η ομαδοποίηση που σχηματίζεται από Κ μεταξύ ν στοιχείων. Ένα στοιχείο μπορεί να επαναληφθεί μια ή περισσότερες φορές και λαμβάνεται υπόψη η τάξη με την οποία τοποθετούνται τα αντικείμενα. Αποδείχνεται ότι ο αριθμός των μεταθέσεων με επαναλήψεις τάξης Κ επί ν στοιχείων δίνεται από τη ν^κ. Δύο στοιχεία (έστω Α και Β), τάξης 3 είναι 2³ = 8, δηλαδή AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB. Οι διατάξεις με επανάληψη 3 στοιχείων (Α, Β, Γ) τάξης 2 είναι 3² = 9, δηλαδή AA, AB, ΑΓ, ΒΑ, BB, ΒΓ, ΓΑ, ΓΒ, ΓΓ. Οι συνδυασμοί με επανάληψη επί ν αντικειμένων τάξης Κ είναι η ομαδοποίηση που σχηματίζεται από Κ μεταξύ ν στοιχείων, στα οποία ένά στοιχείο μπορεί να επαναληφθεί πολλές φορές και όπου δε λαμβάνεται υπόψη η τάξη των αντικειμένων. Αποδείχνεται ότι: Σ_{ν+Κ-1, Κ} = (ν+Κ-1/Κ) = (ν+Κ-) (ν+Κ-2)… (ν+1) ν/Κ! Έτσι, οι συνδυασμοί με επανάληψη επί δύο στοιχείων τάξης 3 είναι Σ_4,3 = 4 x 3 x 2/3! = 4. Αριστερά, φαίνονται όλοι οι δυνατοί συνδυασμοί με τρεις σφαίρες διαφορετικού χρώματος. Δεξιά, οι δυνατές διατάξεις.